1. Field of the Invention
The present invention relates to an apparatus for detecting the collision of a moving object at fast speed and with high accuracy, and is applicable to, for instance, a system for confirming the safety of motion of a taught robot by means of a graphic simulator or the like, a system for determining a collision in the motion of a robot in real time, a system for determining the collision in an unmanned car in real time, or other similar systems.
2. Statement of the Related Art
Conventionally, in the determination of collision of a robot, for instance, a graphic simulator is known which is adapted to display on a screen the configuration of a robot at various positions in a path of its movement or continuously display the motion of a programmed robot on a screen. In this apparatus, the continuous motion of a robot is displayed at an actual moving speed and its motion is simulated, and it is necessary to detect the presence of collisions between two moving robot arms and between the robot arm and a stationary object with high accuracy and at high speed.
Various types of methods are known as methods of determining the collision.
For instance, the following various methods are known: As a first method, as disclosed in Japanese Patent Laid-Open No. 43706/1987, the members of a robot and the work environment are covered with polyhedrons, and the presence of a collision is determined from projected figures of the polyhedrons. As a second method, as disclosed in Japanese Patent Laid-Open No. 99591/1975, the members of a robot and the work environment are expressed by line segments, and the distance between the line segments is computed to determine the presence of a collision. As a third method, as disclosed in the Journal of Robotics Society of Japan, Vol. 6, No. 1, p. 35, the position of movement of a robot or an object in the environment is expressed as a function of time, and the collision between a vertex and a plane or between two edges is determined to be a collision on the basis of that function.
In addition, as disclosed in the Journal of Robotics Society of Japan, Vol. 5, No. 3, p. 21, a fourth method is known in which a robot and an object in the environment are approximated hierarchically by cubes having different sizes, and a collision is determined by checking the relationship of inclusion of the cubes of the two objects. Furthermore, as disclosed in a collection of papers for the 6th Annual Conference of Robotics Society of Japan, p. 105, a fifth method is known in which a robot and an object in the environment are approximated hierarchically by spheres having different radii, and the relationship of inclusion of the spheres having different radii is checked so as to determine the collision of an object.
However, the following drawbacks are experienced with the above-described conventional methods. For instance, with the aforementioned first method, it is impossible to effect collision detection with high accuracy in cases where a member is a concave cube and it is therefore difficult to approximate its shape with a mere cylinder or rectangular parallelepiped. With the second method, although a high-speed determination is possible, modelling is too simple so that the accuracy of collision determination is not good, while, with the third method, the amount of computation becomes large with an increase in the number of faces, resulting in an extreme delay in the processing speed.
In addition, the fourth method has a problem in that although it is based on the technique of a hierarchical structure using a so-called octo tree, since an approximation to a cube is required, the coordinate conversion for expressing a continuously moving object is complicated and takes time. Furthermore, in accordance with the fifth method, a robot and an object in the environment are approximated hierarchically by spheres having different radii so as to simplify the coordinate conversion. As for the method of generating a sphere in a lower rank, however, a regular polyhedron inscribing an upper rank is first determined and the sphere is then determined as one which circumscribes the faces constituting the regular polyhedron and whose center corresponds to the center of gravity of that polyhedron, so that there has been a drawback in that the mechanism of generating the spheres in the lower rank becomes complicated and modeling takes time. Also, there is an additional drawback in that the modeling efficiency is poor and hence modeling takes time due to such causes as an increased number of overlapping areas between spheres, the occurrence of a lower-rank sphere which includes an outer portion of an upper, rank sphere, and the occurrence of a case in which the same sphere belongs to two different upper-rank spheres, or a sphere belongs to a sphere located in an immediately higher rank but does not belong to a sphere located in a rank of a level above two ranks. Furthermore, there is a drawback in that since spheres of a hierarchical structure are generated uniformly with respect to the interior and exterior of objects that are not necessary for describing the shapes of objects subject to modeling, the number of spheres generated becomes numerous, thereby deteriorating the modeling efficiency. Moreover, although the accuracy depends on the radius of the smallest spheres, and the computing speed of collision detection depends on the frequency of determination of collisions between the spheres, i.e., the hierarchical structure of the spheres, since the ratio of radius between the spheres in the mutually adjacent layers is restricted to a fixed ratio, it is difficult to arbitrarily change the hierarchical structure and the radius of the smallest spheres. Hence, the adjustment of the accuracy and the computing speed becomes difficult.